Unprecedented growth in wireless technology has made a tremendous impact on how we communicate. For example, ubiquitous Internet access through wireless has become a reality in many public places, such as airports, malls, coffee shops, hotels, etc. More recently, early adopters have applied wireless technology to obtain broadband access at home, and a number of neighborhood networks have already been launched across the world. Using wireless as the first mile towards the Internet has a big advantage—fast and easy deployment. Therefore it is especially appealing to homes that are out of reach of cable and digital subscriber link-up (DSL) coverage, such as rural and suburban areas. Even for those areas with cable or DSL coverage, providing an alternative for Internet access is certainly useful, as it helps to increase network bandwidth, and suits the diverse needs of different applications.
There has been a recent surge of interest in building wireless neighborhood networks. One such contemplated implementation presents a scheme to build neighborhood networks using standard 802.11b Wi-Fi technology by carefully positioning access points in the community. Such a scheme requires a large number of access points, and direct communication between machines and the access points. This constraint is difficult to meet in real terrains. Another approach to building neighborhood networks is Nokia's Rooftop technology. This scheme provides broadband access to households using a multi-hop solution that overcomes the shortcomings of the standard 802.11b Wi-Fi solution. The idea is to use a mesh network model with each house deploying a radio. This radio solves the dual purpose of connecting to the Internet and also routing packets for neighboring houses. There is a significant cost in deploying and managing Internet Transit Access Points (ITAPs), used as gateways to the Internet, and therefore it is crucial to minimize the required number of ITAPs to provide QoS and fault tolerance guarantees. A similar problem of efficiently bridging a multi-hop wireless network with the Internet also arises in sensor networks, where sensors collect data and send it through a multi-hop wireless network to servers on the Internet via ITAPs. Both of the above applications of wireless networks require careful placement of Internet TAPs to enable good connectivity to the Internet and efficient resource usage. However, to date these problems have not been addressed in the art.
However, a number of studies on placing servers at strategic locations for better performance and efficient resource utilization in the Internet have been conducted. For example, the placement of Web proxies or server replicas to optimize clients' performance has been examined as has the placement problem for Internet instrumentation. The work on server placement, however, optimizes locality in absence of link capacity constraints. This may be fine for the Internet, but is not sufficient for wireless networks since wireless links are often the bottlenecks. Moreover, the impact of wireless interference, and considerations of fault tolerance and workload variation make the ITAP placement problem very different from those studied to date.
It is worth mentioning that the ITAP placement problem can be considered as a facility location type of problem. Facility location problems have been considered extensively in the fields of operation research and approximation algorithms. Approximation algorithms with good worst case behavior have been proposed for different variants of this problem. However, these results do not concern the case where links have capacities. In addition, the effects of wireless interference and variable traffic demands have not been considered in the previous facility location work.
Yet another solution aims to minimize the number of ITAPs for multi-hop neighborhood networks based on the assumption that ITAPs use a Time Division Multiple Access (TDMA) scheme to provide Internet access to users. However, TDMA is difficult to implement in multi-hop networks due to synchronization and channel constraints. Furthermore, a slotted approach could result in decreased throughput due to unused slots. In comparison, a more general and efficient MAC scheme, such as IEEE 802.11 yields completely different designs and increases applicability of the resulting algorithms. Thus there exists a need for a method for determining the placement of ITAPs under the impacts of link capacity constraints, wireless interference, fault tolerance, and variable traffic demands.